DAY 25 試題

問題描述

中位數是一個有序整數列表中的中間值。如果列表的大小為奇數，那麼中位數就是中間的數字；如果列表的大小為偶數，那麼中位數則是中間兩個數字的平均值。

例如，對於 arr = [2,3,4]，中位數是 3；對於 arr = [2,3]，中位數是 (2 + 3) / 2 = 2.5。

實現 MedianFinder 類：

MedianFinder() 初始化 MedianFinder 對象。
void addNum(int num) 將一個數字 num 添加到數據流中。
double findMedian() 返回所有元素的中位數。若答案與實際值的誤差在 10^-5 以內，則視為正確。
範例 1：

• 輸入：
  ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
  [[], [1], [2], [], [3], []]
• 輸出： [null, null, null, 1.5, null, 2.0]
• 解釋：
  MedianFinder medianFinder = new MedianFinder();
  medianFinder.addNum(1); // 數組 arr = [1]
  medianFinder.addNum(2); // 數組 arr = [1, 2]
  medianFinder.findMedian(); // 返回 1.5
  medianFinder.addNum(3); // 數組 arr = [1, 2, 3]
  medianFinder.findMedian(); // 返回 2.0

限制條件：

• -10^5 <= num <= 10^5
• 在調用 findMedian() 之前，數據結構中至少會有一個元素。
• 最多會進行 5 * 10^4 次 addNum() 和 findMedian() 調用。

解題思路

此問題的核心是如何高效地維護數據流中的數據結構，以便在插入新數據後能夠快速地找到中位數。常見解法是使用兩個優先隊列（堆）來解決問題，這樣可以確保每次找到中位數的時間複雜度為 O(1)，而插入數字的時間複雜度為 O(log n)。

解法步驟：
1. 維護兩個堆：

• 使用 最大堆 low 來存放數據流中較小的一半數字。
• 使用 最小堆 high 來存放數據流中較大的一半數字。

2. 平衡兩個堆的大小：

• 每次插入數字後，確保兩個堆的大小相差不超過 1。
• 如果 low 堆的大小大於 high 堆，我們將最大堆的最大值移到最小堆。
• 如果 high 堆的大小大於 low 堆，我們將最小堆的最小值移到最大堆。

3. 計算中位數：

• 如果兩個堆的大小相等，則中位數為兩個堆的頂元素的平均值。
• 如果兩個堆的大小不相等，則中位數為大小較大堆的頂元素。

class MedianFinder {
public:
    MedianFinder() {
    }
    
    void addNum(int num) {
        // 插入到最大堆
        low.push(num);
        // 保持最大堆的所有元素都小於最小堆的元素
        high.push(low.top());
        low.pop();
        
        // 若最小堆的大小超過最大堆，則平衡兩個堆
        if (low.size() < high.size()) {
            low.push(high.top());
            high.pop();
        }
    }
    
    double findMedian() {
        if (low.size() > high.size()) {
            return low.top();
        } else {
            return (low.top() + high.top()) / 2.0;
        }
    }

private:
    priority_queue<int> low; // 最大堆
    priority_queue<int, vector<int>, greater<int>> high; // 最小堆
};

解法重點與分析

1. 兩個堆的設計：

• low 堆是最大堆，負責存儲數據流中較小的一半數字。
• high 堆是最小堆，負責存儲數據流中較大的一半數字。

2. 平衡兩個堆：每次插入數字後，會將新數字先插入 low 堆，然後將最大數移到 high 堆。如果 high 堆的大小超過 low 堆，則將其最小值移回 low 堆，這樣可以保證兩個堆的大小平衡。

3. 時間複雜度：

• 插入數字：每次插入需要 log(n) 的時間，因為需要將數字加入堆中。
• 查詢中位數：時間複雜度為 O(1)，因為可以直接從兩個堆的頂部獲取結果。

4. 空間複雜度：O(n)，因為我們使用了兩個堆來存儲所有的數據。

總結

這個問題通過使用兩個堆來維護數據流的數字，確保每次插入數據後都能夠高效地找到中位數。最大堆存儲較小的一半數字，最小堆存儲較大的一半數字，並通過適時平衡兩個堆來確保中位數的準確性。

以上是第二十五天的自學內容分享，謝謝大家。